#include <bits/stdc++.h>
using namespace std;

/*
3346. 执行操作后元素的最高频率 I
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作  numOperations 次。每次操作中，你可以：

选择一个下标 i ，它在之前的操作中 没有 被选择过。
将 nums[i] 增加范围 [-k, k] 中的一个整数。
在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

 

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2

输出：2

解释：

通过以下操作得到最高频率 2 ：

将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。
示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1

输出：2

解释：

通过以下操作得到最高频率 2 ：

将 nums[1] 增加 0 。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
0 <= k <= 105
0 <= numOperations <= nums.length
*/

// 法一
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int max_freq = 0;

        // 情况1：目标值是原数组中的元素（原逻辑）
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            int left = lower_bound(nums.begin(), nums.end(), x - k) - nums.begin();
            int right = upper_bound(nums.begin(), nums.end(), x + k) - nums.begin();
            int t = right - left; // 区间内元素总数
            
            int l = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
            int r = upper_bound(nums.begin(), nums.end(), x) - nums.begin();
            int c = r - l; // 原x的数量
            
            max_freq = max(max_freq, min(t, c + numOperations));
        }

        // 情况2：目标值是重叠区间内的新值（补充逻辑）
        int j = 0;
        for (int i = 0; i < n; ++i) {
            // 找到最大j，使nums[j]的调整范围与nums[i]的调整范围有重叠
            while (j < n && nums[j] - k <= nums[i] + k) {
                j++;
            }
            int m = j - i; // 区间[i..j-1]的元素总数（均可调整到同一新目标值）
            // 最大频率：取区间元素数与可操作次数的较小值（新目标值无原元素，需操作所有m个）
            max_freq = max(max_freq, min(m, numOperations));
        }

        return max_freq;
    }
};

// 法二
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        int n = nums.size();
        int mx = *max_element(nums.begin(), nums.end()); // 找到数组最大值，确定统计范围
        
        // data[i]：数字i在nums中的出现次数（频率统计）
        vector<int> data(mx + 1);
        for (auto num : nums) {
            data[num]++;
        }
        
        // pre[i]：前缀和数组，pre[i] = sum(data[0..i])，用于快速计算区间元素总数
        vector<int> pre(mx + 1);
        pre[0] = 0;
        for (int i = 1; i <= mx; i++) {
            pre[i] = pre[i - 1] + data[i];
        }
        
        int ans = 0;
        // 遍历每个可能的目标值i（需在nums的数值范围内）
        for (int i = 1; i <= mx; i++) {
            int right = min(i + k, mx); // 目标i的调整范围右边界（不超过最大值）
            int left = max(0, i - k - 1); // 目标i的调整范围左边界（不小于0，用于前缀和计算）
            int total = pre[right] - pre[left]; // 范围[i-k, i+k]内的元素总数
            
            // 当前目标i的最大频率：原频率data[i] + 最多可操作的其他元素（不超过区间内其他元素数和可操作次数）
            ans = max(ans, min(total - data[i], numOperations) + data[i]);
        }
        return ans;
    }
};
